package algo;

import model.tsp.Problem;
import model.tsp.Solution;
import util.CheckUtils;
import util.PrinterUtils;
import util.SelectUtils;

import java.util.*;

public class AdaptiveLargeNeighborhoodSearch extends LocalSearch3 {

    private int nodeNum;//城市节点数量

    private int destroyOperator, repairOperator;//算子
    private double[] destroyWeights;//毁坏算子权重
    private double[] repairWeights;//修复算子权重
    private int[] destroyCnt;//毁坏算子使用次数
    private int[] repairCnt;//修复算子使用次数

    private static final double lambda = 0.5;
    private static final int destroyOperatorNum = 4;
    private static final int repairOperatorNum = 2;

    public void solve() {
        Solution initSolution = initial();
        PrinterUtils.printTspResult("alns init", initSolution);
        Solution finalSolution = improve(initSolution);
        PrinterUtils.printTspResult("alns final", finalSolution);
        CheckUtils.check(finalSolution, distance);
        //plot(finalSolution);
    }

    public AdaptiveLargeNeighborhoodSearch(Problem problem) {
        super(problem);
        this.nodeNum = problem.getNodeNum();
        this.destroyWeights = new double[destroyOperatorNum];
        Arrays.fill(destroyWeights, 1);
        this.repairWeights = new double[repairOperatorNum];
        Arrays.fill(repairWeights, 1);
        this.destroyCnt = new int[destroyOperatorNum];
        this.repairCnt = new int[repairOperatorNum];
    }

    @Override
    protected Solution improve(Solution solution) {
        Solution bestSolution = solution.copy();
        Solution currentSolution = solution.copy();
        int k = 0;
        int kMax = 1000;

        while (k++ < kMax) {
            List<Integer> x = new ArrayList<>(currentSolution.getPermutation());
            // ruin and recreate
            Set<Integer> removedNodes = selectAndDestroy(x, 10);
            selectAndRepair(x, removedNodes);

            Solution newSolution = new Solution(x, calculateFitness(x));

            // update the operator weight
            double score = 0;
            if (newSolution.getCost() < bestSolution.getCost()) {
                bestSolution = newSolution.copy();
                currentSolution = newSolution.copy();
                score = 4.0;
            } else if (newSolution.getCost() < currentSolution.getCost()) {
                currentSolution = newSolution.copy();
                score = 2.0;
            } else {
                score = 1.0;
            }

            destroyWeights[destroyOperator] = (1 - lambda) * destroyWeights[destroyOperator]
                    + lambda * (score / destroyCnt[destroyOperator]);
            repairWeights[repairOperator] = (1 - lambda) * repairWeights[repairOperator]
                    + lambda * (score / repairCnt[repairOperator]);

            System.out.format("第%d次迭代最优值：%d\n", k, bestSolution.getCost());
        }

        return bestSolution;
    }

    private Set<Integer> selectAndDestroy(List<Integer> permutation, int removedNum) {
        // 删除路径节点
        destroyOperator = SelectUtils.rouletteSelectOperator(destroyWeights, random);//roulette(destroyWeights);
        Set<Integer> removedNodes;
        if (destroyOperator == 0) {
            removedNodes = randomRemove(permutation, removedNum);
        } else if (destroyOperator == 1) {
            removedNodes = worstRemove(permutation, removedNum);
        } else if (destroyOperator == 2){
            removedNodes = neighborhoodRemove(permutation, removedNum);
        } else {
            removedNodes = continuousRemove(permutation, removedNum);
        }

        destroyCnt[destroyOperator] += 1;
        return removedNodes;
    }

    private void selectAndRepair(List<Integer> permutation, Set<Integer> insertNodes) {
        // 修复路径节点
        repairOperator = SelectUtils.rouletteSelectOperator(repairWeights, random);//roulette(repairWeights);
        if (repairOperator == 0) {
            randomInsert(permutation, insertNodes);
        } else {
            greedyInsert(permutation, insertNodes);
        }
        repairCnt[repairOperator] += 1;
    }


    ///////////////////// ruin operator ///////////////////////////////////
    private Set<Integer> randomRemove(List<Integer> x, int removedNum) {
        Set<Integer> removedNodes = new HashSet<>();
        while (removedNodes.size() < removedNum) {
            int index = random.nextInt(nodeNum - 1) + 1;
            if (!removedNodes.contains(index)) {
                removedNodes.add(index);
            }
        }
        x.removeAll(removedNodes);
        return removedNodes;
    }

    private Set<Integer> worstRemove(List<Integer> x, int removedNum) {
        Set<Integer> removedNodes = new HashSet<>();
        for (int i = 0; i < removedNum; i++) {
            int dist = 0;
            int index = -1;
            for (int j = 1; j < x.size(); j++) {
                int newDist;
                if (j == (x.size() - 1)) {
                    newDist = distance[j - 1][j] + distance[j][0] - distance[j - 1][0];
                } else {
                    newDist = distance[j - 1][j] + distance[j][j + 1] - distance[j - 1][j + 1];
                }

                if (newDist > dist) {
                    dist = newDist;
                    index = j;
                }
            }

            removedNodes.add(x.get(index));
            x.remove(index);
        }

        return removedNodes;
    }

    private Set<Integer> continuousRemove(List<Integer> x, int removedNum) {
        Set<Integer> removedNodes = new HashSet<>();
        int index = random.nextInt(x.size() - removedNum - 1) + 1;
        int k = 0;
        while (k++ <= removedNum) {
            removedNodes.add(x.get(index));
            index++;
        }
        x.removeAll(removedNodes);
        return removedNodes;
    }

    private Set<Integer> neighborhoodRemove(List<Integer> x, int removedNum) {
        List<Integer> removedNodes = new ArrayList<>();
        List<Integer> candidates = new ArrayList<>();
        int target = random.nextInt(x.size() - 1) + 1;

        for (int i = 1; i < x.size(); i++) {
            int dist = distance[target][i];
            if (removedNodes.size() < removedNum) {
                removedNodes.add(x.get(i));
                candidates.add(dist);
            } else {
                int maxDist = Collections.max(candidates);
                if (dist < maxDist) {
                    int index = candidates.indexOf(maxDist);
                    candidates.set(index, dist);
                    removedNodes.remove(index);
                    removedNodes.add(x.get(i));
                }
            }
        }
        x.removeAll(removedNodes);
        return new HashSet<>(removedNodes);
    }

    ///////////////////// recreate operator ///////////////////////////////////
    private void randomInsert(List<Integer> x, Set<Integer> insertNodes) {
        for (Integer node : insertNodes) {
            int index = random.nextInt(x.size() - 1) + 1;
            x.add(index, node);
        }
    }

    private void greedyInsert(List<Integer> x, Set<Integer> insertNodes) {
        for (Integer node : insertNodes) {
            int dist = Integer.MAX_VALUE;
            int index = -1;
            for (int i = 0; i < x.size(); i++) {
                List<Integer> newX = new ArrayList<>(x);
                newX.add(i, node);
                int newDist = calculateFitness(newX);
                if (newDist < dist) {
                    dist = newDist;
                    index = i;
                }
            }
            x.add(index, node);
        }
    }


}
